The present invention relates to an elliptic curve encryption processing method, an elliptic curve encryption processing apparatus, and a program for realizing high-speed elliptic curve encryption.
Recently, with advances in network communication and electronic commerce, security protection in communication has become an important issue. One method of security protection is encryption technology and, at present, communications using various encryption techniques are performed in practice.
The encryption methods are broadly classified into common key methods and public key methods. The common key methods are also called “symmetrical encryption methods”, in which both the originator and the receiver hold a common key. As a representative method of the common key method, there is DES (Data Encryption Standard). The features of the DES algorithm are that encryption and decryption can be performed using substantially the same algorithm.
In contrast to this common key encryption, a construction in which the keys of the originator and the receiver are different is a public key method or an asymmetrical encryption method. In the public key encryption method, unlike the common key encryption method which uses a common key for encryption and decryption, a secret key which must be kept secret needs only to be possessed by one specific person. Therefore, the public key encryption method is advantageous in managing keys. However, since the data processing speed of the public key encryption method, is generally slower than that of the common key encryption method, the public key encryption method is often used for objects with a small amount of data, such as the distribution of the secret key or a digital signature. RSA (Rivest-Shamir-Adleman) encryption is a representative example of the public key encryption method. RSA uses a product of two very large prime numbers (for example, 150 digits), and the difficulty of factorizing the product of two large prime numbers (for example, 150 digits) into prime numbers is used.
The public key encryption method has a construction in which a public key can be used for an unspecified number of the general public and in which a method of using a certificate, which certifies whether or not the public key to be distributed is valid, that is, a so-called public key certificate, is often used. For example, a user A generates a public key and secret key pair, sends the generated public key to a certificate authority, and obtains a public key certificate from the certificate authority. The user A makes the public key certificate public. An unspecified user obtains the public key from the public key certificate after undergoing a predetermined procedure, encrypts a document, etc., and sends it to the user A. The user A is a system in which the encrypted document, etc., is decrypted using the secret key. Furthermore, the user A is a system in which a signature is attached to a document, etc., by using the secret key, an unspecified user obtains the public key from the public key certificate after undergoing a predetermined procedure, and the verification of the signature is performed.
The public key certificate is a certificate which is issued by the certificate authority (CA) or the issuer authority (IA) in the public key encryption method, and is also a certificate which is created such that, as a result of a user submitting a user ID, the public key, etc., to the certificate authority, the certificate authority adds information, such as the ID of the certificate authority and the period of validity, and furthermore, the signature of the certificate authority is added.
As the public key encryption method, in addition to the above-described RSA method, discrete logarithm encryption, which uses the difficulty of the discrete logarithm problem in a case where n is a prime number, is known. This discrete logarithm encryption is used for the DSA (Digital Signature Standard), which is a known digital signature standard in the United States. Furthermore, the elliptic curve cryptography (ECC), which was proposed by V. Miller and N. Koblitz, has recently attracted attention due to its security and high speed. Elliptic curve cryptography using a 160-bit key is said to have a strength comparable to a 1024-bit key in RSA.
Generally, elliptic curve cryptography uses an elliptic curve represented by y2=x3+ax+b (4a3+27b2≠0) on a prime field and an elliptic curve represented by y2+xy=x3+ax2+b (b≠0) on two extension fields. A set in which a point at infinity (O) is added to the points on these curves forms a finite group with respect to addition, and the point at infinity (O) becomes the identity element thereof. Hereafter, addition of points on this finite group is indicated by “+”. The addition P+Q of two different points P and Q on this finite group is called “addition of points”, and the addition P+P=2P of a point P and a point P is called “double addition of points”. Furthermore, the computation for determining the points P+P+ . . . +P=kP, in which the point P is added k times, is called “scalar multiplication of points”.
It is known that the scalar multiplication of points can be formed by using addition of points and double addition of points. The addition method of points, the double addition method of points, and the scalar multiplication of points on the affine coordinate system (x, y) and the projective coordinates (X, Y, Z) on an elliptic curve on a prime field and on elliptic curves on two extension fields are described in “IEEE P1363/D13 Standard Specification for Public Key Cryptography”.
Furthermore, a method (P. Montgomery, “Speeding the Pollard and Elliptic Curve Method of Factorization”, Mathematics of Computation, Vol. 48, No. 177, pp. 243–264 (1987)) of performing at high speed the scalar multiplication of points by using a Montgomery elliptic curve represented by By2=x3+Ax2+x ((A2−4)B≠0) on a prime field, which was introduced to perform factorization into prime numbers, has been proposed. Hereafter, this technique is called the “Montgomery method on an elliptic curve on a prime field”.
According to this method, in the affine coordinate system, when the addition point of two different points P0(x0, y0) and P1(x1, y1) is denoted as point P2=P1+P0, if P3(x3, y3)=P1(x1, y1)−P0(x0, y0) is known, then x2 can be determined on the basis of:x2=(x0x1−1)2/(x3(x0x1)2)
Furthermore, when the point of double addition of the point P0(x0, y0) is denoted as point P2(x2, y2)=2P0, then x2 can be determined on the basis of:x2=(x02−1)2/(4x0(x22+Ax0+1))In this manner, the addition method of points and the double addition method of points can be formed without using the y coordinate.
Here, in general, since division on a prime field has a higher calculation cost compared to multiplication on a prime field, when conversion into the projective coordinate system (X, Y, Z) is performed while assuming that x=X/Z and y=Y/Z, the Montgomery elliptic curve becomes:BY2Z=X3+AX2Z+XZ2 
At this time, when the addition point of two different points P0(X0, Y0, Z0) and P1(X1, Y1, Z1) is denoted as P2(X2, Y2, Z2)=P1(X1, Y1, Z1)+P0(X0, Y0, Z0), if P3(X3, Y3, Z3)=P1(X1, Y1, Z1)−P0(X0, Y0, Z0) is known, then (X2, Z2) can be determined on the basis of:X2=Z3((X0−Z0)(X1+Z1)+(X0+Z0)(X1−Z1))2 Z2=X3((X0−Z0) (X1+Z1)−(X0+Z0) (X1−Z1))2 Furthermore, when the point of the double addition of the point P0(X0, Y0, Z0) is denoted as point P2(X2, Y2, Z2)=2P0, then, assuming that C=(A+2)/4, (X2, Z2) can be determined on the basis of:X2=(X0+Z0)2 Z2=((X0+Z0)2−(X0−Z0)2)((X0−Z0)2+C((X0+Z0)2−(X0−Z0)2))In this manner, the addition method of points and the double addition method of points can be formed without using the Y coordinate.
In order to form a scalar multiplication kP of points by using the above addition method of points and the double addition method of points in the Montgomery elliptic curve on a prime field, a point which is a difference between two points in the addition of points needs to be known. By taking note of this, the following is performed. The initial two points are denoted as {T0, T1}={P, 2P}, and k is subjected to dyadic expansion. When the bits from the bit next to the highest-order bit to the lowest-order are all 0, {2T0, T0+T1} is determined from {T0, T1} so as to be formed as a new {T0, T1}. When the bits are all 1, {T0+T1, 2T1} is determined from {T0, T1} so as to be formed as a new {T0, T1}. This is repeated. Then, the final TO becomes kP. At this time, T1−T0=P always holds.
ECDSA (Elliptic Curve Digital Signature Algorithm) is a representative example of an electronic signature method using elliptic curve encryption. In the signature verification process of ECDSA, a calculation for determining the x coordinate of the addition point kP+lQ of scalar multiplication points of two different points is required.
In order to calculate the x coordinate of kP+lQ using the Montgomery method on an elliptic curve on a prime field, the following is performed. First, kP and lQ are determined by the Montgomery method on an elliptic curve on a prime field in accordance with the above-described technique. Thereafter, the point kP and the point lQ are added together. However, since the point of the difference between two points is not known, the above-described addition method of points cannot be used. For this reason, it is necessary to determine the x coordinate of kP+lQ by using another addition method after the y coordinate or the Y coordinate of each of kP and lQ is recovered.
Furthermore, a technique (J. Lopez and R. Dahab, “Fast Multiplication on Elliptic Curve over GF(2m) without Precomputation”, Cryptographic Hardware and Embedded Systems, LNCS 1717, pp. 316–327 (1999)) of performing at high speed the scalar multiplication of points by the same technique as for the Montgomery elliptic curve on a prime field on an elliptic curve y2+xy=x3+ax2+b (b≠0) on two extension fields has been proposed. Hereafter, this is called the “Montgomery method on elliptic curves on two extension fields”. Also, in this technique, in order to calculate the x coordinate of kP+lQ, it is necessary to determine the x coordinate of kP+lQ after the y coordinate or the Y coordinate of each of kP and lQ is recovered.
As described above, in the Montgomery method on an elliptic curve on a prime field and in the Montgomery method on elliptic curves on two extension fields, scalar multiplication of points can be calculated at high speed. However, in the calculation of kP+lQ required when the ECDSA signature is to be created, a process of restoring the y coordinate or the Y coordinate of kP+lQ is required.